{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Time to Complete Trips"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumTime"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #完成旅途的最少时间"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个数组&nbsp;<code>time</code>&nbsp;，其中&nbsp;<code>time[i]</code>&nbsp;表示第 <code>i</code>&nbsp;辆公交车完成 <strong>一趟</strong><strong>旅途</strong>&nbsp;所需要花费的时间。</p>\n",
    "\n",
    "<p>每辆公交车可以 <strong>连续</strong> 完成多趟旅途，也就是说，一辆公交车当前旅途完成后，可以 <strong>立马开始</strong>&nbsp;下一趟旅途。每辆公交车 <strong>独立</strong>&nbsp;运行，也就是说可以同时有多辆公交车在运行且互不影响。</p>\n",
    "\n",
    "<p>给你一个整数&nbsp;<code>totalTrips</code>&nbsp;，表示所有公交车&nbsp;<strong>总共</strong>&nbsp;需要完成的旅途数目。请你返回完成 <strong>至少</strong>&nbsp;<code>totalTrips</code>&nbsp;趟旅途需要花费的 <strong>最少</strong>&nbsp;时间。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>time = [1,2,3], totalTrips = 5\n",
    "<b>输出：</b>3\n",
    "<strong>解释：</strong>\n",
    "- 时刻 t = 1 ，每辆公交车完成的旅途数分别为 [1,0,0] 。\n",
    "  已完成的总旅途数为 1 + 0 + 0 = 1 。\n",
    "- 时刻 t = 2 ，每辆公交车完成的旅途数分别为 [2,1,0] 。\n",
    "  已完成的总旅途数为 2 + 1 + 0 = 3 。\n",
    "- 时刻 t = 3 ，每辆公交车完成的旅途数分别为 [3,1,1] 。\n",
    "  已完成的总旅途数为 3 + 1 + 1 = 5 。\n",
    "所以总共完成至少 5 趟旅途的最少时间为 3 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>time = [2], totalTrips = 1\n",
    "<b>输出：</b>2\n",
    "<strong>解释：</strong>\n",
    "只有一辆公交车，它将在时刻 t = 2 完成第一趟旅途。\n",
    "所以完成 1 趟旅途的最少时间为 2 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= time.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= time[i], totalTrips &lt;= 10<sup>7</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-time-to-complete-trips](https://leetcode.cn/problems/minimum-time-to-complete-trips/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-time-to-complete-trips](https://leetcode.cn/problems/minimum-time-to-complete-trips/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3]\\n5', '[2]\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, time: List[int], totalTrips: int) -> int:\n",
    "        left = 1\n",
    "        right = totalTrips * max(time)\n",
    "\n",
    "        def is_valid(x):\n",
    "            count = 0\n",
    "            for t in time:\n",
    "                count += x // t\n",
    "                if count >= totalTrips:\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        while left < right:\n",
    "            mid = (right+left) // 2\n",
    "            if is_valid(mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid+1\n",
    "\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, time: List[int], totalTrips: int) -> int:\n",
    "        def check(t, tol):\n",
    "            for ti in time:\n",
    "                tol -= (t // ti)\n",
    "                if tol <= 0: return True\n",
    "            return False\n",
    "        \n",
    "        l, r = 1, max(time) * totalTrips\n",
    "        while l < r:\n",
    "            m = (l + r) // 2\n",
    "            if check(m, totalTrips): r = m\n",
    "            else: l = m + 1\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, time: List[int], totalTrips: int) -> int:\n",
    "        left = min(time)\n",
    "        right = min(time) * totalTrips\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            total = 0\n",
    "            for t in time:\n",
    "                total += mid // t\n",
    "            if total >= totalTrips:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, time: List[int], totalTrips: int) -> int:\n",
    "        def trips(mid):\n",
    "            trips = 0\n",
    "            for i in time:\n",
    "                if mid // i == 0:\n",
    "                    break\n",
    "                trips += mid // i\n",
    "            return trips >= totalTrips\n",
    "\n",
    "        time.sort()\n",
    "        left = 1\n",
    "        right = totalTrips * max(time)\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if trips(mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, time: List[int], totalTrips: int) -> int:\n",
    "        l, r = 0, max(time) * totalTrips\n",
    "        while l + 1 < r:\n",
    "            m = l + r >> 1\n",
    "            if sum([m//x for x in time]) >= totalTrips:\n",
    "                r = m\n",
    "            else:\n",
    "                l = m\n",
    "        return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, time: List[int], totalTrips: int) -> int:\n",
    "        maxT = min(time) * totalTrips + 1 #45\n",
    "        rate = sum([1/x for x in time]) \n",
    "        minT = floor(totalTrips/rate)\n",
    "        while minT < maxT:\n",
    "            midT = minT + (maxT - minT) //2\n",
    "            midTrips = sum([midT//x for x in time])\n",
    "            if midTrips < totalTrips:\n",
    "                minT = midT + 1\n",
    "            else:\n",
    "                maxT = midT\n",
    "                \n",
    "        return minT"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, time: List[int], totalTrips: int) -> int:\n",
    "        def hanshu(k):\n",
    "            res=0\n",
    "            for s in time:\n",
    "                res+=k//s\n",
    "            return res\n",
    "        return bisect_left(range(max(time)*totalTrips),totalTrips,key=hanshu)\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, time: List[int], totalTrips: int) -> int:\n",
    "        left, right = 0, 10 ** 14 + 1\n",
    "        while left < right - 1:\n",
    "            mid = (left + right) // 2\n",
    "            k = 0\n",
    "            for n in time:\n",
    "                k += mid // n\n",
    "            if k >= totalTrips:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, time: List[int], totalTrips: int) -> int:\n",
    "        n = len(time)\n",
    "        def check(t: int) -> bool:\n",
    "            f = [0]*n\n",
    "            for i in range(n):\n",
    "                f[i] = f[i-1] + t//time[i]\n",
    "            return f[-1] >= totalTrips\n",
    "        left = 1\n",
    "        right = max(time)*totalTrips\n",
    "        while left<right:\n",
    "            mid  = (left+right)//2\n",
    "            if check(mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid+1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, time: List[int], totalTrips: int) -> int:\n",
    "        \n",
    "        def check(t):\n",
    "            cnt = 0\n",
    "            for period in time:\n",
    "                cnt += t//period\n",
    "            return cnt>=totalTrips\n",
    "        \n",
    "\n",
    "        l = 0\n",
    "        r = max(time) * totalTrips\n",
    "\n",
    "        while l < r:\n",
    "            mid = (l+r)//2\n",
    "            \n",
    "            if check(mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid +1\n",
    "        \n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, time: List[int], totalTrips: int) -> int:\n",
    "        def count(k: int) -> int:\n",
    "            cnt = 0\n",
    "            for t in time:\n",
    "                cnt += k // t\n",
    "            return cnt\n",
    "\n",
    "        left, right = 1, max(time) * totalTrips\n",
    "        while left < right:\n",
    "            mid = (left + right) >> 1\n",
    "            if count(mid) < totalTrips:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def minimumTime(self, time: List[int], totalTrips: int) -> int:\n",
    "        lo, hi = 1, max(time) * totalTrips\n",
    "\n",
    "        while lo < hi:\n",
    "            md = lo + (hi - lo) // 2\n",
    "            if sum([md // t for t in time]) >= totalTrips: \n",
    "                hi = md\n",
    "            else:\n",
    "                lo = md + 1\n",
    "        return lo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, time: List[int], totalTrips: int) -> int:\n",
    "        \n",
    "        left = min(time)\n",
    "        right = totalTrips*left\n",
    "        while left<=right:\n",
    "            mid = (left+right)>>1\n",
    "            if sum([(mid)//t for t in time]) >=totalTrips:\n",
    "                right = mid-1\n",
    "            else:\n",
    "                left = mid+1\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, time: List[int], totalTrips: int) -> int:\n",
    "        l = 1\n",
    "        ans = max(time) * len(time) * totalTrips\n",
    "        r = max(time) * len(time) * totalTrips\n",
    "        while l <= r:\n",
    "            mid = l + (r - l) // 2\n",
    "            t = sum([mid // i for i in time])\n",
    "            if t >= totalTrips:\n",
    "                r = mid - 1 \n",
    "                ans = min(ans , mid)\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
